class AVLNode:
    """AVL树的节点类"""

    def __init__(self, val):
        self.val = val
        self.left = None  # 左子节点
        self.right = None  # 右子节点
        self.height = 1  # 节点高度，新节点初始高度为1


class AVLTree:
    """AVL树类，实现插入、查询和删除功能"""

    def __init__(self):
        self.root = None  # 根节点初始化为空

    def get_height(self, node):
        """获取节点的高度，空节点高度为0"""
        if not node:
            return 0
        return node.height

    def get_balance(self, node):
        """计算节点的平衡因子（左子树高度 - 右子树高度）"""
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def right_rotate(self, y):
        """右旋转操作"""
        x = y.left
        T2 = x.right

        # 执行旋转
        x.right = y
        y.left = T2

        # 更新高度
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

        # 返回新的根节点
        return x

    def left_rotate(self, x):
        """左旋转操作"""
        y = x.right
        T2 = y.left

        # 执行旋转
        y.left = x
        x.right = T2

        # 更新高度
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        # 返回新的根节点
        return y

    def _insert(self, node, val):
        """内部插入方法，递归实现"""
        # 1. 执行标准的BST插入
        if not node:
            return AVLNode(val)
        elif val < node.val:
            node.left = self._insert(node.left, val)
        else:  # val >= node.val
            node.right = self._insert(node.right, val)

        # 2. 更新当前节点的高度
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 3. 计算平衡因子，检查是否不平衡
        balance = self.get_balance(node)

        # 4. 如果不平衡，处理四种情况

        # 左左情况 - 右旋转
        if balance > 1 and val < node.left.val:
            return self.right_rotate(node)

        # 右右情况 - 左旋转
        if balance < -1 and val > node.right.val:
            return self.left_rotate(node)

        # 左右情况 - 先左旋转再右旋转
        if balance > 1 and val > node.left.val:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        # 右左情况 - 先右旋转再左旋转
        if balance < -1 and val < node.right.val:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        # 如果平衡，返回当前节点
        return node

    def _get_min_node(self, node):
        """获取以node为根的树中的最小值节点（最左节点）"""
        current = node
        while current.left:
            current = current.left
        return current

    def _delete(self, node, val):
        """内部删除方法，递归实现"""
        # 1. 执行标准的BST删除
        if not node:
            return node  # 节点不存在

        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:  # 找到要删除的节点
            # 情况1：只有一个子节点或没有子节点
            if not node.left:
                return node.right
            elif not node.right:
                return node.left

            # 情况2：有两个子节点
            # 找到中序后继（右子树中的最小值节点）
            temp = self._get_min_node(node.right)
            node.val = temp.val
            # 删除中序后继
            node.right = self._delete(node.right, temp.val)

        # 如果树只有一个节点，删除后为空
        if not node:
            return node

        # 2. 更新当前节点的高度
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 3. 计算平衡因子
        balance = self.get_balance(node)

        # 4. 如果不平衡，处理四种情况

        # 左左情况
        if balance > 1 and self.get_balance(node.left) >= 0:
            return self.right_rotate(node)

        # 左右情况
        if balance > 1 and self.get_balance(node.left) < 0:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        # 右右情况
        if balance < -1 and self.get_balance(node.right) <= 0:
            return self.left_rotate(node)

        # 右左情况
        if balance < -1 and self.get_balance(node.right) > 0:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        return node

    def _search(self, node, val):
        """内部查询方法，递归实现"""
        # 基本情况：根为空或值在根节点
        if not node or node.val == val:
            return node

        # 值大于根的值，在右子树中查找
        if val > node.val:
            return self._search(node.right, val)

        # 值小于根的值，在左子树中查找
        return self._search(node.left, val)

    # 公开方法
    def insert(self, val):
        """插入值到AVL树"""
        self.root = self._insert(self.root, val)

    def delete(self, val):
        """从AVL树中删除值"""
        self.root = self._delete(self.root, val)

    def search(self, val):
        """查询值是否在AVL树中，存在返回True，否则返回False"""
        return self._search(self.root, val) is not None

    def inorder_traversal(self):
        """中序遍历，返回排序后的列表"""
        result = []

        def _traverse(node):
            if node:
                _traverse(node.left)
                result.append(node.val)
                _traverse(node.right)

        _traverse(self.root)
        return result


# 测试代码
if __name__ == "__main__":
    avl = AVLTree()

    # 插入测试
    values = [9, 5, 10, 0, 6, 11, -1, 1, 2]
    for val in values:
        avl.insert(val)
        print(f"插入 {val} 后，中序遍历: {avl.inorder_traversal()}")

    # 查询测试
    print("\n查询测试:")
    print(f"是否存在 10: {avl.search(10)}")  # True
    print(f"是否存在 3: {avl.search(3)}")  # False

    # 删除测试
    print("\n删除测试:")
    avl.delete(10)
    print("删除 10 后，中序遍历: ", avl.inorder_traversal())
    print(f"是否存在 10: {avl.search(10)}")  # False

    avl.delete(1)
    print("删除 1 后，中序遍历: ", avl.inorder_traversal())

    avl.delete(5)
    print("删除 5 后，中序遍历: ", avl.inorder_traversal())